package com.cloud.code.算法.排序.插入排序;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {

        Integer[] data = {1, 4, 2, 6, 3};
//        insert(data);
        insertSort(data);
//        insertSortFromLast(data);
    }

    public static <E extends Comparable> void insert(E[] data) {

        int length = data.length;
        for (int i = 0; i < length; i++) {

            E temp = data[i];
            int j;
            for (j = i; j > 0; j--) {
                if(temp.compareTo(data[j-1]) < 0){
                    data[j-1] = data[j];
                }
            }
            data[j] = temp;

        }
        System.out.println(Arrays.toString(data));
    }


















    public static <E extends Comparable> void insertSort(E[] data) {
        int length = data.length;
        for (int i = 0; i < length; i++) {
            E e = data[i];
            int j;
            for (j = i; j > 0 && e.compareTo(data[j - 1]) < 0; j--) {
                data[j] = data[j - 1];
            }
            data[j] = e;
            System.out.println(Arrays.toString(data));
        }


    }


    public static <E extends Comparable> void insertSortFromLast(E[] data) {
        int length = data.length;
        for (int i = length - 1; i >= 0; i--) {
            E e = data[i];
            int j;
            for (j = i; j < length - 1 && e.compareTo(data[j + 1]) > 0; j++) {
                data[j] = data[j + 1];
            }
            data[j] = e;
            System.out.println(Arrays.toString(data));
        }


    }
}
